// Created by WXX on 2021/12/14 22:02
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

/**
 * 执行用时：56 ms, 在所有 C++ 提交中击败了95.27%的用户
 * 内存消耗：41 MB, 在所有 C++ 提交中击败了50.30%的用户
 */
// 先放置出现次数较多的数，中间隔着一个数
typedef pair<int, int> PII;

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int> &barcodes) {
        unordered_map<int, int> cnt;
        for (auto x : barcodes) cnt[x]++;

        vector<PII> q;
        for (auto &[k, v] : cnt) q.push_back({v, k});
        sort(q.begin(), q.end(), greater<PII>());

        int n = barcodes.size();
        vector<int> res(n);
        int k = 0;
        for (auto &p : q) {
            while (p.first--) {
                res[k] = p.second;
                k += 2;
                if (k >= n) k = 1;
            }
        }
        return res;
    }
};

void OutputBasicArray1D(vector<int> nums) {
    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {

    vector<int> barcodes = {1, 1, 1, 2, 2, 2};
    OutputBasicArray1D(Solution().rearrangeBarcodes(barcodes));

    return 0;
}
